package 力扣._00周赛._367周赛.问题2;

public class Solution {
    public String shortestBeautifulSubstring(String s, int k) {
        //滑动窗口
        int sum = 0;  //窗口内1的数量
        int l = 0, r = 0;
        int goal_l = -1, goal_r = -1;  //最优的
        while (l < s.length() && r < s.length()) {
            while (l < s.length() && s.charAt(l) == '0') l++;
            if (s.charAt(r) == '1') {
                sum++;
            }
            if (sum == k) {
                //和最优的作比较
                if (goal_l == -1) {
                    goal_l = l;
                    goal_r = r;
                } else {
                    if (goal_r - goal_l > r - l) {  //长度更短
                        goal_l = l;
                        goal_r = r;
                    } else if(goal_r - goal_l == r - l){//字典序更小
                        for (int i = 0; i <= r - l; i++) {
                            if (s.charAt(goal_l + i) > s.charAt(l + i)) {
                                goal_l = l;
                                goal_r = r;
                                break;
                            }else if(s.charAt(goal_l + i) < s.charAt(l + i))
                                break;
                        }

                    }
                }
                //左加一
                l++;
                while (l < s.length() && s.charAt(l) == '0') l++;
                sum--;
                r++;
            } else if (sum < k) {
                r++;
            }
        }
        if (goal_l <= goal_r && goal_r < s.length() && goal_l >= 0)
            return s.substring(goal_l, goal_r + 1);
        return "";
    }

    public static void main(String[] args) {
        String s = "110101000010110101";
        int k = 3;
        String s1 = new Solution().shortestBeautifulSubstring(s, k);
        System.out.println(s1);
    }
}
